---
title: "城堡问题"
created: 2025-11-28
tags:
  - 算法
---

# 城堡问题

## 题目 [城堡问题](https://www.acwing.com/solution/content/140306/)

```
    1   2   3   4   5   6   7
   #############################
 1 #   |   #   |   #   |   |   #
   #####---#####---#---#####---#
 2 #   #   |   #   #   #   #   #
   #---#####---#####---#####---#
 3 #   |   |   #   #   #   #   #
   #---#########---#####---#---#
 4 #   #   |   |   |   |   #   #
   #############################
           (图 1)

   #  = Wall
   |  = No wall
   -  = No wall

方向：上北下南左西右东。
```

图1是一个城堡的地形图。

请你编写一个程序，计算城堡一共有多少房间，最大的房间有多大。

城堡被分割成 m\*n个方格区域，每个方格区域可以有0~4面墙。

注意：墙体厚度忽略不计。

输入格式

第一行包含两个整数 m 和 n，分别表示城堡南北方向的长度和东西方向的长度。

接下来 m 行，每行包含 n 个整数，每个整数都表示平面图对应位置的方块的墙的特征。

每个方块中墙的特征由数字 P 来描述，我们用**1表示西墙，2表示北墙，4表示东墙，8表示南墙，P 为该方块包含墙的数字之和。**

例如，如果一个方块的 P 为3，则 3 = 1 + 2，该方块包含西墙和北墙。

城堡的内墙被计算两次，方块(1,1)的南墙同时也是方块(2,1)的北墙。

输入的数据保证城堡至少有两个房间。

输出格式

共两行，第一行输出房间总数，第二行输出最大房间的面积（方块数）。

数据范围

![[image-88e04834.png]]

#### 输入样例：

```text
4 7
11 6 11 6 3 10 6
7 9 6 13 5 15 5
1 10 12 7 13 7 5
13 11 10 8 10 12 13
```

#### 输出样例：

```text
5
9
```

## 思路分析

每个方格可以被看作是图中的一个节点，方格中的墙表示节点间是否有边相连（即是否可以直接从一个方格到达另一个方格）

1表示西墙，2表示北墙，4表示东墙，8表示南墙，P 为该方块包含墙的数字之和（1西 10北 100东 1000南）可以用位运算来判断墙的存在。如果一个方格的值为3（即二进制的`11`），那么我们知道这个方格有西墙（位1）和北墙（位2）。因此，我们可以用`g[i][j] & 1`来判断西墙是否存在，用`g[i][j] & 2`来判断北墙是否存在，以此类推

结合枚举4个方向就可以写成 `if (g[x][y] >> i & 1) continue;`

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

const int N=60;

int g[N][N];

bool st[N][N];

int size;

int n,m;

int dx[4]={0,-1,0,1};

int dy[4]={-1,0,1,0};

bool isVaild(int x,int y){

	return x>=1 && x<=n && y>=1 && y<=m && !st[x][y];//这里从1开始

}

void dfs(int x,int y){

	for(int i=0;i<4;i++){

		if(g[x][y]>>i&1)//四个方向是否有墙

			continue;

		int nx=x+dx[i],ny=y+dy[i];

		if(isVaild(nx,ny)){

			size++;

			st[nx][ny]=true;

			dfs(nx,ny);

			//只能用一次 不能回溯

		}

	}

}

int main()

{

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	cin>>n>>m;

	for(int i=1;i<=n;i++){

		for(int j=1;j<=m;j++){

			cin>>g[i][j];

		}

	}

	int ans=0,res=0;

	for(int i=1;i<=n;i++){

		for(int j=1;j<=m;j++){

			if(!st[i][j]){

				size=0;

				dfs(i,j);

				ans++;

				res=max(res,size);

			}

		}

	}

	cout<<ans<<endl<<res<<endl;

	return 0;

 }
```

bfs写法

```cpp
#include <iostream>

#include <queue>

using namespace std;

typedef pair <int,int> PII;

const int N = 60;

int dx[] = {0,-1,0,1},dy[] = {-1,0,1,0};

int n,m,ans = 0,res = 0;

int g[N][N];

bool vis[N][N];

int bfs (int i,int j) {

    queue <PII> q;

    q.push ({i,j});

    vis[i][j] = true;

    int cnt = 0;

    while (!q.empty ()) {

        PII t = q.front ();

        q.pop ();

        cnt++;

        for (int k = 0;k < 4;k++) {

            if (g[t.first][t.second] >> k & 1) continue;

            int x = t.first + dx[k],y = t.second + dy[k];

            if (vis[x][y]) continue;

            q.push ({x,y});

            vis[x][y] = true;

        }

    }

    return cnt;

}

int main () {

    cin >> n >> m;

    for (int i = 1;i <= n;i++) {

        for (int j = 1;j <= m;j++) cin >> g[i][j];

    }

    for (int i = 1;i <= n;i++) {

        for (int j = 1;j <= m;j++) {

            if (!vis[i][j]) {

                ans++;

                res = max (res,bfs (i,j));

            }

        }

    }

    cout << ans << endl << res << endl;

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[Lake Counting S|Lake Counting S]] 🏠 [[00-刷题理模型]] ➡️ [[山峰和山谷|山峰和山谷]]